package 算法面试;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by LiuChang on 2020/1/7
 */
public class Solution {
    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1;
        int index2 = n - 1;
        int index = m + n - 1;

        while (index >= 0) {
            if (index1 < 0) {
                nums1[index] = nums2[index2];
                index2--;
            } else if (index2 < 0) {
                nums1[index] = nums1[index1];
                index1--;
            } else if (nums2[index2] > nums1[index1]) {
                nums1[index] = nums2[index2];
                index2--;
            } else if (nums2[index2] <= nums1[index1]) {
                nums1[index] = nums1[index1];
                index1--;
            }
            index--;
        }

    }

    public static int superEggDrop(int K, int N) {
        return dp(K, N);
    }

    public static Map<Integer, Integer> cashMap = new HashMap<Integer, Integer>();

    public static int dp(int K, int N) {
        if (N == 0) {
            return 0;
        }
        if (K == 1) {
            return N;
        }

        int cashKey = K * 1000000 + N;
        if (cashMap.containsKey(cashKey)) {
            return cashMap.get(cashKey);
        }

        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= N; i++) {
            int max = Math.max(dp(K - 1, i - 1), dp(K, N - i));
            min = Math.min(min, max + 1);
        }

        cashMap.put(cashKey, min);


        return min;

    }

    public static void main(String[] args) {
        System.out.println(superEggDrop(2, 2));
       /* int[] nums1 = new int[]{1, 2, 3, 0, 0, 0};
        int[] nums2 = new int[]{2, 5, 6};
        int m = 3;
        int n = 3;

        merge(nums1, m, nums2, n);*/
    }


}
